# 下一个更大元素III: https://leetcode-cn.com/problems/next-greater-element-iii/

class Solution:
    def nextGreaterElement(self, n: int) -> int:
        """
            可以参考31号算法题, 一模一样的思路，那题我有详细的题解
        """

        def reverse(nums, low, high):
            while low < high:
                nums[low], nums[high] = nums[high], nums[low]
                low += 1
                high -= 1

        n = list(str(n))
        leg = len(n)
        for i in range(leg-1, 0, -1):
            if n[i-1] < n[i]:
                print(n[i-1])
                # 寻找后面最接近 n[i-1]，但是大于 n[i-1]的值
                for j in range(leg-1, -1, -1):
                    if n[i-1] < n[j]:
                        n[i-1], n[j] = n[j], n[i-1]
                        break
                # 逆序i后面的
                reverse(n, i, leg-1)
                break
        else:
            # 没有更大的，直接返回-1
            return -1
        
        # 开始拼接这个数字，超过32位正整数，就返回 -1
        rst = 0
        for i in n:
            # if rst > (2**31 -1) // 10:
            #     return -1
            rst = rst*10 + ord(i) - ord("0")
            if rst > 2**31 -1:
                return -1
                
        return rst











